Atari Mega Archive 1/Atari Mega Archive - Volume 1.iso/games/stello11.lzh/DOC/STELLO.TXT

Text File | 1994-07-04 | 24KB | 482 lines

Hello everybody.

Here  is version 1.10 of my Othello/Reversi game Stello  (ST-Othello  or
Super-Othello or whatever you like best).

Files:
  README            (short description of stello)
  STELLO.PRG        (Othello for 68000)
  STELLO30.PRG      (Othello for 68030)
  STEENG.RSC        (english rsc.)
  STEGER.GER        (german rsc.)
  STEDAN.RSC        (danish rsc.)
  BLACK.LIB         (black opening lib)
  WHITE.LIB         (white opening lib)
  DISCS\*.BIN       (different discs)
  BOARD\COL2\*.IMG  (pictures for 2 colors)
  BOARD\COL4\*.IMG  (pictures for 4 colors)
  BOARD\COL16\*.IMG (pictures for 16 colors)
  DOC\REGISTER.TXT  (Send this to me please)
  DOC\STELLO.TXT    (you are reading it)
  DOC\WHATSNEW      (what is new in this version)
  GAM\BADPOS.GAM    (set response time to infinity and wait)
  GAM\PLY22.GAM                      do
  GAM\END.GAM                        do
  GAM\WOW64.GAM                      do

History:
  5 years ago.

  Beeing very interested in game theory,  and the game of Othello, i had
  (in   vain)  for  a  long  time  searched  for  a  good   and   strong
  implementation  of  this  game  for  the  Atari  computer  line.   Not
  succeding i said to myself,  why not write one myself. Had i known how
  difficult  and  timeconsuming it would be,  i would probably  not  had
  started.  Anyway i bought a book called advanced Pascal in which there
  was a tiny othello game.  It was quickly adopted to my atari computer,
  and  of cause then i played some matches against it.  What a  bommer!!
  It  played so bad that i could not belive it.  Looking at  the  source
  code i had to admit that i really didn't understand what was going on.
  I needed to learn about the fundamentals before i could make a  better
  program.  I then began to study the theory behind game  playing,  such
  as  the  alfa/beta minimax algorithm and many other  related  objects.
  During the next two years i developed the fundamental algorithms,  and
  implemented  it  in  Pascal,  and where it was  needed  for  speed  in
  assembler.  Writing in Prospero Pascal was not anything i would  whish
  for  my worst enemies.  After two years of work (in my spare  time)  i
  had  a  working version of a Othello game which had  a  primitive  Gem
  interface.  The searching algorithms were quite good,  but the "brain"
  was  not working so good.  Once in a while it would loose  control  of
  the  game due to something that i didn't quite  understand.  You  must
  understand,  that while i tried to make my program better,  i also had
  to  develop my own understanding of the game.  I can clearly say  that
  it had made me a much better Othello player to write this program.  In
  these  two  years  i concentrated on learning the  theory  behind  the
  searching  algoritmes  and the different techniques  to  optimize  the
  minimax algorithme.  (There is still room for improvement, for example
  it  was  just  during the last three months  that  i  implemented  the
  zerowidth  modifikation to minimax,  and i still need  to  investigate
  the hash table techniques).  What i needed was a better  understanding
  of the game itself.  Something then happend which were the major force
  behind  the increase in playing strength during the last three  years.
  I  read an article of Paul Rosenblaum who had made a  Othello  program
  of  remarkable strength.  In this article he made a very good  analyse
  of  the  game itself,  and made some suggestions about  the  ways  one
  could  implement  a  evaluation function which  could  understand  the
  features  of the game.  After studing his article i began  implmenting
  his  ideas  and  improving upon them.  Eureka,  my  program  got  much
  stronger.  Programming in pascal was not fun any more,  so i  switched
  to  Turbo  C,  and later to Pure C.  What a joy programming  now  was,
  compiling  the  program  was  now a  matter  of  seconds  compared  to
  minutes.  The  last two years whent by,  and i improved the  interface
  beyond  recognation  and  optimized  the shit  out  of  the  searching
  algorithms.  The brain got a facelift,  which means that i implemented
  some  ideas  of  my  own,  that made a much  stronger  player  of  the
  program.  I  did  this  by making the  program  avoid  the  inherently
  unstable evaluations which most othello programs do,  and that  really
  made  it come up amongst the best programs in the world.  So now  here
  it  is.  After  five  years  of  development  i  will  release  it  as
  Shareware.  i  really hope thet you will enyoy it,  and that you  will
  gratify a hardworking programmer with his modest shareware fee.

Tecnicals:

  The  search  is based on the alfa/beta - minimax  algorithm.  It  uses
  several   heuristics  to  improve  the  search   strategi.   Iterative
  deepening,  response  killer table,  saving the game tree  (all  moves
  are saved, as long as there is memory, the program reserves all memery
  except 10%,  so if you have 4 megabyte it could take 3.6 megabyte  for
  the  tree  of  moves alone) and sorting  the  moves  dynamically  when
  everything  else fails.  This reduces the brancing factor  to  between
  3.0  to 4.5.  It really depends on the position.  In the end game  the
  banching factor is between 1.8 to 2.4.

  The  evaluation is based on several independent  components,  such  as
  mobility,  stability and corner and edge disks. The program is capable
  of  solving  most  endgame positions when there is  only  16-14  moves
  left  (depending  on  computer and position,  some  positions  can  be
  solved  when  20 moves are missing).  It does so by using  the  highly
  optimized  search algoritms,  which in the end game is  improved  with
  the  recursive  zerowidth alfa/beta-minimax algorithm.  On  a  TT  the
  endgame  routine searches the game tree,  with 15000-20000 nodes  per.
  second.  A  TT has a clock of 32 MH.  A instruction neads at  least  2
  clock  cycles  to  complete.   This  gives  32000000/(20000*2)  =  800
  instructions  per  node.  For every node the program has to  sort  the
  moves,  make at least one move and evaluate the move. Then call itself
  recursively to do so for the rest of the nodes.  Doing so in just  800
  instructions  is,  in my own opinion,  rather good.  The speed of  the
  normal  search  is  1500-4500 nodes pr  second.  You  can  not  really
  compare  this  with other programs,  as it depends on  the  evaluation
  function.  My evaluation function, dosen't just evaluate one node, but
  investigates  the  possible responds and counterresponds  to  be  sure
  that  the position is approximately stable,  wich really improves  the
  playing strenght..

Playing strength:

  To test how strong my program was,  i made a little testmatch  against
  the program Thor.  Thor is one of the best Othollo playing programs in
  the  world,  having  participated in several  turnements,  and  usally
  ending  amongst  the top programs.  I made the two  programs  play  10
  different positions against each other,  as both black and white. This
  is 20 games in all.  The play level was turnement,  which means 30 min
  for  one game.  The results follow.

             Stello        Thor         Thor         Stello
           | Black  | p |  White | p |  Black | p |  White | p |
  ---------------------------------------------------------------
  game  1. |   41   | 1 |   23   | 0 |   44   | 1 |   20   | 0 |
  game  2. |   30   | 0 |   33   | 1 |    7   | 0 |   57   | 1 |
  game  3. |   54   | 1 |   10   | 0 |   14   | 0 |   50   | 1 |
  game  4. |   53   | 1 |   11   | 0 |   15   | 0 |   49   | 1 |
  game  5. |   58   | 1 |    6   | 0 |   27   | 0 |   37   | 1 |
  game  6. |   22   | 0 |   42   | 1 |   19   | 0 |   45   | 1 |
  game  7. |   38   | 1 |   26   | 0 |   19   | 0 |   45   | 1 |
  game  8. |   25   | 0 |   39   | 1 |   23   | 0 |   41   | 1 |
  game  9. |   29   | 0 |